Ian Wienand: Distance to 1 million people
On a recent trip up the Oregon coast, a friendly doorman at our
hotel in Portland was inquiring about our trip. When we mentioned we
passed through Bandon, OR, he quipped that Bandon was the place
furthest from a city of one million people in the USA. I guess a
normal person would just think "oh, that's interesting" and move on,
but it has been plaguing me ever since.
Firstly, I had to find what cities in the USA had more than 1
million people. Luckily Wolfram Alpha gives the answer:
From this, I can see that Bandon, about a third of the way up the
Oregon coast, is a pretty good candidate. However, probably not the
best; I get the feeling the real point that is the furthest from any
city of 1 million people is actually somewhere in the central-middle
of Montana.
However, we can also fiddle the program slightly to disprove the
point about Bandon. The numbers show the closest large city to Bandon
is LA, at ~1141km. Taking another point we suspect to be more remote;
the closest large city to Portland (where we met the doorman) is also
LA at ~1329km. So to reach the closest large city you have to travel
further from Portland than Bandon, so Bandon is not the
furthest place in the USA from a city of one million people. Myth
busted!
- Chicago,Illinois
- Dallas,Texas
- Houston,Texas
- Los Angeles,California
- New York, New York
- Philadelphia,Pennsylvania
- Phoenix,Arizona
- San Antonio,Texas
- San Diego,California
From this, I can see that Bandon, about a third of the way up the
Oregon coast, is a pretty good candidate. However, probably not the
best; I get the feeling the real point that is the furthest from any
city of 1 million people is actually somewhere in the central-middle
of Montana.
However, we can also fiddle the program slightly to disprove the
point about Bandon. The numbers show the closest large city to Bandon
is LA, at ~1141km. Taking another point we suspect to be more remote;
the closest large city to Portland (where we met the doorman) is also
LA at ~1329km. So to reach the closest large city you have to travel
further from Portland than Bandon, so Bandon is not the
furthest place in the USA from a city of one million people. Myth
busted!
Serve creates goroutines via the go
keyword; each of which tries to get a slot in the channel. In the
example there are only 3 slots, so it acts like a semaphore of count
3. When done, each thread returns its slot to the channel, which
allows anyone blocked to be woken and continued.
This instantly reminded me of the very first thing you need to do
if you ever want to pass 
Look familiar? Instead of a blocking push of a number into a slot
into a channel, you make a blocking IPC call to a remote server.
My point here is that both take the approach of sharing memory via
communication. When using IPC, you bundle up all your information
into the available slots in the IPC message and send it. When using a
channel, you bundle your information into an entry in the channel and
call your goroutine. Receiving the IPC is the same as draining a
channel - both result in you getting the information that was bundled
into it by the caller.
This seems to give quite useful results with a bare minimum of
effort, and most importantly no tricky floating point math. For
example, on the standard Unix words with a 2048 entry
hash-table, the standard DJB hash came out very well (as expected)
The image above gives some idea of how it works. We can examine
relocations with the readelf tool.
As shown above, the GOT ensures the abstraction required so symbols
can be diverted as expected. Each entry is essentially a pointer to
the real data (hence the extra dereference in the code above). Since
the GOT is at a fixed offset from the program code, it can use an IP
relative address to gain access to the table entries.
This extra reference is obviously slower; however for the most part
I imagine the overhead would be essentially immeasurable and is
required for "generic" operation. If you have figured the cost of
indirection through the GOT is the major bottleneck of your program, I
imagine you wouldn't be reading this and would already be considering
strategies to remove it!
The next question is why this works on plain old x86-32.
Inspecting the code reveals why:
In the first example, there was not enough information to tell if
the function would ever be able to be overridden, hence a PLT entry
had to be created and the function called through it (disassemble it
to see the details!). With correct symbol visibility attributes,
there is enough information to know that
common_but_not_part_of_api is never to be overridden, hence
the PLT (and the associated costs of trampolining) can be avoided.
The internal attribute is even stricter; it says that this
function will never be called from outside this module (for
example, we might pass the address of
common_but_not_part_of_api to anyone). This can lead to even
better code, because on many architectures transitioning to another
module might involve flipping global pointer registers or other
similarly expensive operations.
So that's how symbol binding and visibility attributes can work
together to get you the best performance possible from your
program!
